typedstream
StreamTable
	HashTable
Object
[20c]
typedstream
[915c]
typedstream
	HashTable
Object
PlotController
HeaderClass
%%%%i@@
genericobject_nib
theScrollView
thePlotView
FirstResponder
firstnib
checkSpelling:
alignSelCenter:
	unscript:
pasteFont:
runPageLayout:
superscript:
copyRuler:
	copyFont:
selectAll:
pasteRuler:
toggleRuler:
showGuessPanel:
alignSelLeft:
paste:
performClose:
arrangeInFront:
subscript:
copy:
alignSelRight:
delete:
orderFrontColorPanel:
underline:
performMiniaturize:
PlotView
viewnib
crossCursor
textCell
points
InitTemp
Stop1
delegate
Iterations
PathL
Freeze
CoolingOn:
plot:
Nuke:
clear:
DoRoute:
CoolingOff:
Stop:
[9361c]
typedstream
	HashTable
Object
NXImage
PlotterAppIcon
NXBitmapImageRep
NXImageRep
iissss00
[576c]
UUUUUUUUUUG
UUUUUUUUUUT
UUUUUUUUUUT
NibData
@@@@s
Storage
{*@@}
	[42{*@@}]
File's Owner
CustomObject
Application
MainMenu
MenuTemplate
*@*@ccc
Salesman
Matrix
Control
	Responder
@:@iiii
MenuCell
ButtonCell
ActionCell
Info...
	Helvetica
Paste
Select All
ff@@#::s
submenuAction:
Bitmap
	menuArrow
Print
Traveling Salesman
WindowTemplate
iiii***@s@
Window
[12@]
ScrollView
ClipView
ciifffcfffs
[157c]{\rtf0\ansi{\fonttbl\f0\fswiss Helvetica;}
\margl40
\margr40
\pard\tx960\tx1920\tx2880\tx3840\tx4800\tx5760\tx6720\tx7680\tx8640\tx9600\f0\b0\i0\ul0\fs24 
NXCursor
NXibeam
Scroller
_doScroller:
@@@ffs
Button
Plot cities
Clear map 
	TextField
TextFieldCell
Cities
Helvetica-Bold
CustomView
PlotView
Find & Show Route
Break
	Clear All
NXradio
NXradioH
Radio
FormCell
Present Path length:
Present Temperature:
Initial Temperature:
Test for Freezing:
Trials Between Plottings:
Field:
Latent cooling
ScrollingText
Field2
Field
Field3
Present Path length!
Present Temperature&
Initial Temperature*
Test for Freezing.
Trials Between Plottings2
Field1:
PlotControllerInstance
PlotController
 Info
Panel
^This application interface uses Plotter, by Matt Morse,
NeXT Technical Publications Department
Times-Roman
Traveling Salesman Problem
;Nolan R. Davis and Joseph Jeffery
Naval Research Laboratory
Times-BoldItalic
%An Application of Simulated Annealing
Times-Bold
Button1_TOZTHcT
Field4hT
Field5mT
Field6pT
[2934c]{\rtf0\ansi{\fonttbl\f0\fswiss Helvetica;}
\margl40
\margr40
{\colortbl\red0\green0\blue0;}
\pard\tx520\tx1060\tx1600\tx2120\tx2660\tx3200\tx3720\tx4260\tx4800\tx5320\f0\b0\i0\ul0\fs24\fc0 This application addresses the Traveling Salesman Problem, which requires that a salesman visiting N different cities find the shortest possible route that passes through each city once and only once. It uses Simulated Annealing, an algorithm for efficiently solving nonlinear optimization problems.  This problem is NP-complete:  The computation time increases exponentially as the number of cities increases.  For the Traveling Salesman Problem, there are (N-1)! /2 distinct routes to search. For example, with 14 cities, there are 3.1 billion routes. In this demonstration, Simulated Annealing can find a good solution usually within a few thousand trials. Although not guaranteed to get the best solution, Simulated Annealing will find a good one, which is often all one really needed, while saving a great deal of time. The above example is on the order of a million times faster than checking all possible routes.\
The locations of the cities can be entered into the scroll view (Cities) or can be added to it by mouse clicking the map (maximum of 30 cities). When clicking on the map the cursor point whose coordinates appear just below the map can be dragged to whatever location on the map before being released and added to the list. An already existing city can be moved by clicking within its circle and dragging it.  When entering cities directly through the scroll view one must first display them using "Plot Cities" before one can find the route.\
Initial Temperature and Test for Freezing are parameters used to control how the algorithm runs and the quality of the final path. Generally speaking, the higher these values the more optimal the final route and the longer needed to run.  As initial estimates, Initial Temperature is set at 5 times the initial path length, and Test is set at 10 times the number of cities.\
In this application the default cooling schedule reduces the temperature inverse-proportionally to the number of iterations.  In addition, one can turn on a ``Latent Heat'' cooling schedule that allows the temperature to decrease based on changes in the path length [ Davis et al., ``An adaptive cooling schedule for simulated annealing with application to multiple-constraint time-domain beamforming'', J. Acoust. Soc. Am., Suppl. 1, Vol. 88 (1990)].  This cooling schedule has been found to have a nearly exponential cooling rate in spurts, and can significantly decrease the number of iterations required to reach a good solution.\
Trials Between Plotting determines how often the intermediate trial routes will be plotted. Any negative number causes it to plot only the final route. Note the more you plot the slower it will run. Runs usually have several hundred to several thousand trials.
{i*@@@}
[25{i*@@@}]
hide:
terminate:
copy:
paste:
selectAll:
clear:
plot:
theScrollViewQ
thePlotViewQ
delegate
makeKeyAndOrderFront:
printPSCode:
DoRoute:
Nuke:	
textCell
PathL
CoolingOn:
Freeze
InitTemp
CoolingOff:
Iterations